The present invention generally relates to a system and method for tracking computer data. More particularly, it relates to a system and method that tracks computer data using at least one table having all the node entries for each data set, wherein each node entry has a linked list identification, a previous pointer, and a next pointer.
Linked lists are commonly used to keep reference positions for a computer data set. Nodes entries are generally found in the linked lists, and they are reference points of data elements. Nodes entries are updated as data structure changes, which allows the computer to track the various positioning points of the elements as the data structure changes. Under a doubly-linked list implementation, each node entry has both a previous pointer and a next pointer. The previous pointer indicates the previous linked position of the node entry, and the next pointer indicates the next linked position. Two doubly linked list methods are known in the art.
Referring to FIG. 1, a prior method for implementing doubly linked lists is shown. A node entry 10 generally includes a next pointer 14 and a previous pointer 16. Under this method, the node entry 10 is typically placed in the first few bytes of the data structure of the actual data set 12. The general order of the data structure begins with a next pointer 14, a previous pointer 16, and data set 12 respectively, which will all be referred to as a data element 19. Data elements A, B, and C are shown in FIG. 1 as an example, and all the data elements 19 are kept in a single linked list 18. For each data set 12, a node entry 10 of a next pointer 14 and a previous pointer 16 is located at the beginning of the data structure. The start of the node entry 10 and the start of the data set 12 share the same address in memory. The tracking of the data is straight forward. For example, as indicated by the arrows, the next pointer 14 of data element A refers to data element B, and next pointer of data element B refers to data element C. Similarly, in the reverse direction, the previous pointer 16 of data element C refers to data element B, and the previous pointer of data element B refers to data element A.
Because of this given arrangement, a node entry 10 can be easily deleted by redefining the node entries. For example, to delete data element B from the linked list 18 involves only two steps. The next pointer of data element A must be redefined to refer to the data element C. Similarly, the previous pointer of data element C must also be redefined to refer to data element A. More specifically, the program notations are xe2x80x9cB.prev.next=B.nextxe2x80x9d and xe2x80x9cB.next.prev=B.prevxe2x80x9d. This arrangement provides a constant time delete O(1), meaning that the time it takes to delete a node entry 10 is independent of how many nodes are in a single linked list 18. The time remains constant regardless of the number of data elements 19 in a linked list 18. As a result, the node entries 10 can be updated more easily and efficiently.
One problem with this method is that it allows the data element 19 to exist only in one linked list 18 at a time. Although the module processing speed is faster, it is less preferred for more complex data implementations because data elements cannot exist in multiple linked lists.
Turning to FIG. 2, another prior method for implementing doubly linked lists using multiple lists is shown. Rather than having the node entry 10 be embedded in the actual data set 12, this method uses a data pointer 20, which basically makes the node entry point to the actual data set. Unlike the node entry 10 in the previous method having both a next pointer 14 and a previous pointer 16, the node entry in this method has a next pointer, a previous pointer and a data pointer 20. As shown, multiple linked lists 18 can be used and a particular data set 12 can belong to multiple lists at the same time. Two linked lists L and M are shown as an example. In practice, thousands of linked lists 18 may be used.
However, a problem with this method is that in order to delete a data set 12 from a linked list 18, all the node entries in the linked list must be searched, which can be time consuming when hundreds of node entries in a single linked list must be searched to find the data set""s corresponding node entry 10. For example, to delete data set B from linked list L, all the node entries must be searched in linked list L in order to find and delete the node entry with a data pointer to data set B. This method uses a O(n) delete time, wherein n is the number of node entries in a single linked list. In other words, the delete time factor of a node entry 10 is dependent upon the number of node entries in a linked list.
One problem with this method is that it is extremely inefficient and greater processing resources are needed to complete the same tasks as the previous method. As a result, the module processing speed is sacrificed because of the complexity.
Accordingly, a primary object of the present invention is to provide an improved system and method for tracking computer data that allows a data element to belong to multiple linked lists while the processing time is independent of number of data elements in any of the linked lists.
Another object of the present invention is to provide an improved system and method for tracking computer data that can update node entries more easily.
Still another object of the present invention is to provide an improved system and method for tracking computer data that is more efficient in terms of processing speed.
Yet another object of the present invention is to provide an improved system and method for tracking computer data that allows for data to belong to multiple linked lists without sacrificing processing speed.
The present invention generally relates to a system and a method for tracking computer data. More particularly, it relates to a system and method that tracks computer data that uses at least one table having all the node entries. Each node entry has a linked list identification, a previous pointer, and a next pointer. With the use of the table and node entries having a linked list identification, the present invention is able to provide an improved system and method for tracking computer data that allows data to belong to multiple linked lists but without sacrificing processing speed.
The present invention includes a system having at least one data set and at least one node table for each data set. Furthermore, it includes at least one node entry for each node table, wherein each node entry having a linked list identification, a previous pointer, and a next pointer. Lastly, at least one linked list referencing said at least one node entry is also included.
The present invention further includes a method including steps of creating at least one node entry designating a previous pointer and a next pointer for each data set, maintaining at least one node table having all the node entries for each data set, assigning said linked list identification to each said node entry, and maintaining at least one linked list for each said linked list identification.